/**
 * 素数是大于 1 的自然数，只能被 1 和它本身整除（没有余数）。isPrime()通过使用 for 循环编写函数来完成以下程序。成功后，程序会打印“成功！”。
 *   它检查偶数。我们知道这些都不是素数（2 除外）。
 *   它检查所有数字以x查看它们是否是除数。非质数（合数）必须至少有一个小于或等于其平方根的除数。std::sqrt(x)（在 <cmath> 标头中）返回 的平方根x。
 * 
 * Why do we check up to the square root of a number to determine if the number is prime?
 *   If a number n is not a prime, it can be factored into two factors a and b:
 *   n = a * b
 *   Now a and b can't be both greater than the square root of n, since then the product a * b would be greater than sqrt(n) * sqrt(n) = n. 
 *   So in any factorization of n, at least one of the factors must be less than or equal to the square root of n, and if we can't find any factors less than or equal to the square root, n must be a prime.
 * 
 */

#include <cassert>
#include <cmath> // for std::sqrt
#include <iostream>

// optimized version
bool isPrime(int x)
{
    if (x <= 1)     // if x is negative, 0, or 1 then the number is not prime
        return false;
    if (x == 2)     // the number 2 is the only even prime
        return true;
    if (x % 2 == 0) // any other even number is not prime
        return false;

    // For any number 3 or greater, test odd values (this is why we add 2)
    // between 3 and sqrt(x) to see if they are a divisor
    // Also see https://stackoverflow.com/questions/5811151/why-do-we-check-up-to-the-square-root-of-a-number-to-determine-if-the-number-is
    for (int test{ 3 }; test <= std::sqrt(x); test += 2)
    {
        if (x % test == 0) // if x is evenly divisible
            return false;  // then this number isn't prime
    }

    return true; // if we didn't find any divisors, then x must be prime
}

int main()
{
    assert(!isPrime(0));
    assert(!isPrime(1));
    assert(isPrime(2));
    assert(isPrime(3));
    assert(!isPrime(4));
    assert(isPrime(5));
    assert(isPrime(7));
    assert(!isPrime(9));
    assert(isPrime(11));
    assert(isPrime(13));
    assert(!isPrime(15));
    assert(!isPrime(16));
    assert(isPrime(17));
    assert(isPrime(19));
    assert(isPrime(97));
    assert(!isPrime(99));
    assert(isPrime(13417));

    std::cout << "Success!\n";

    return 0;
}